package lcof2

import "math/rand"

// RandomizedSet https://leetcode.cn/problems/FortPu/
type RandomizedSet struct {
	elem   []int
	exists map[int]int
}

// Constructor Initialize your data structure here.
func Constructor() RandomizedSet {
	return RandomizedSet{
		exists: make(map[int]int),
	}
}

// Insert Inserts a value to the set. Returns true if the set did not already contain the specified element.
func (t *RandomizedSet) Insert(val int) bool {
	if _, ok := t.exists[val]; ok {
		return false
	}
	t.exists[val] = len(t.elem)
	t.elem = append(t.elem, val)
	return true
}

// Remove Removes a value from the set. Returns true if the set contained the specified element.
func (t *RandomizedSet) Remove(val int) bool {
	if _, ok := t.exists[val]; !ok {
		return false
	}
	idx := t.exists[val]
	// first map, second array.
	t.exists[t.elem[len(t.elem)-1]] = idx
	delete(t.exists, val)
	t.elem[idx], t.elem[len(t.elem)-1] = t.elem[len(t.elem)-1], t.elem[idx]
	t.elem = t.elem[0 : len(t.elem)-1]
	return true
}

// GetRandom Get a random element from the set.
func (t *RandomizedSet) GetRandom() int {
	return t.elem[rand.Intn(len(t.elem))]
}
